Tristate logic is often used in large scale integrated logic circuits, usually to implement a multiplexing function with smaller area and delay. The drawback of using tri-state logic gates in logic design is that extra precautions need to be taken to prevent the occurrence of either of the following conditions during circuit operation: Condition 1: a “bus-conflict” condition in which two or more of the tri-state elements driving the bus are active at the same time; and Condition 2: a “floating bus” condition in which all of the tri-state elements driving the bus are inactive. Both conditions are undesirable in large scale integrated circuits because they can result in a) excessive levels of power consumption and b) unknown logic values that can interfere with chip testing techniques that capture and compress circuit values into a signature register. A number of methods have been developed to test for proper bus operation in semiconductor devices.
Ma U.S. Pat. No. 5,373,514 granted on Dec. 13, 1994 for “Three-State Bus Structure and Method for Generating Test Vectors While Avoiding Contention and/or Floating Outputs on the Three-State Bus” describes a method for generating test vectors that will not put tri-state buses in a conflicting or floating condition. However, the method does not identify tri-state buses that will be conflict-free and floating-free under any combination of circuit inputs.
Maamari et al U.S. Pat. No. 5,420,871 granted on May 30, 1995 for “Method for Maintaining Bus Integrity During Testing” describes a different method for generating test vectors that will not put tri-state buses in a conflicting condition. As a preliminary step in the method, an implication-based procedure is performed to identify tri-state buses that are conflict-free under any combination of circuit inputs. While efficient, the procedure is not always conclusive, i.e. it may fail to identify some conflict-free tri-state buses.
Koseko et al in a paper entitled “Tri-State Bus Conflict Checking Method for ATPG Using BDD”, published in the Proceedings of the 1993 International Conference on Computer-Aided Design, pp 512-515, propose a method using Binary Decision Diagrams (BDDs) to identify tri-state buses that are conflict-free and floating-free under any combination of inputs. The method is conclusive, however BDDs are known to explode in size in the presence of some circuit structures such as multipliers, thus requiring excessive amounts of processing to come to a conclusion.
Pixley et al U.S. Pat. No. 5,572,535 granted on Nov. 5, 1996 for “Method and Data Processing System for Verifying the correct operation of a Tri-State Multiplexer in a Circuit Design” improved on the Koseko et al. approach by using cut sets to reduce BDD sizes. However, in many cases, the selected cut set yields inconclusive results requiring the BDDs to be re-evaluated for several cut sets before a conclusion can be reached, thereby offsetting the benefits of having smaller BDDs. Consequently, there continues to be a need for better and alternate solutions to the problem of conclusively identifying tri-state buses which violate the aforementioned conflict-free and floating-free conditions.